package com;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description: 二叉搜索树与双向链表
 * User: YJ
 * Date: 2024-4-03
 * Time: 15:15
 */
public class ConvertExe {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null)
            return null;
        //设置栈用于遍历
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode head = null;
        TreeNode pre = null;
        //确认第一个遍历到最左，即为首位
        boolean isFirst = true;
        while (pRootOfTree != null || !s.isEmpty()) {
            //直到没有左节点
            while (pRootOfTree != null) {
                s.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }
            pRootOfTree = s.pop();
            //最左元素即表头
            if (isFirst) {
                head = pRootOfTree;
                pre = head;
                isFirst = false;
                //当前节点与上一节点建立连接，将pre设置为当前值
            } else {
                pre.right = pRootOfTree;
                pRootOfTree.left = pre;
                pre = pRootOfTree;
            }
            pRootOfTree = pRootOfTree.right;
        }
        return head;
    }
}
